#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

bool compless(int a, int b){
    int absa = a>0? a : -a;
    int absb = b>0? b : -b;
    if(absa == absb)
        return a > b;
    return absa < absb;
}

vector<Interval> merge(vector<Interval> &intervals) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int posLen = intervals.size()*2;
    int *pos = new int[posLen];

    for(int i=0; i<intervals.size(); ++i){
        pos[i*2] = intervals[i].start+1;
        pos[i*2+1] = -intervals[i].end-1;
    }
    sort(pos, pos+posLen, compless);
    vector<Interval> res;
    int cur = 0;
    int beginPos = -1;
    for(int i=0; i<posLen; ++i){
        if(pos[i]>=0){
            if(cur == 0){
                beginPos = pos[i];
            }
            ++cur;
        }
        else{
            if(cur == 1){
                // get a new interval
                Interval newInter(beginPos-1, -pos[i]-1);
                res.push_back(newInter);
            }
            --cur;
        }
    }

    delete []pos;
    return res;
}


int main(){

}